- polynomially bounded algorithm
- полиномиально ограниченный алгоритм
Англо-русский словарь по вычислительной технике и информационным технологиям - 4-е изд.. Сергей Орлов .
polynomially bounded algorithm
Смотреть что такое "polynomially bounded algorithm" в других словарях:
Randomized algorithm — Part of a series on Probabilistic data structures Bloom filter · Skip list … Wikipedia
NP (complexity) — Diagram of complexity classes provided that P ≠ NP. The existence of problems outside both P and NP complete in this case was established by Ladner.[1] In computational complexity theory, NP is one of the most fundamental complexity classes. The… … Wikipedia
Linear programming — (LP, or linear optimization) is a mathematical method for determining a way to achieve the best outcome (such as maximum profit or lowest cost) in a given mathematical model for some list of requirements represented as linear relationships.… … Wikipedia
Clique problem — The brute force algorithm finds a 4 clique in this 7 vertex graph (the complement of the 7 vertex path graph) by systematically checking all C(7,4)=35 4 vertex subgraphs for completeness. In computer science, the clique problem refers to any of… … Wikipedia
Karp-Lipton theorem — The Karp–Lipton theorem in complexity theory states that if the boolean satisfiability problem (SAT) can be solved by Boolean circuits with a polynomial number of logic gates, then :Pi 2 , = Sigma 2 , and therefore mathrm{PH} , = Sigma 2 ,.That… … Wikipedia
Church–Turing thesis — Church s thesis redirects here. For the constructive mathematics assertion, see Church s thesis (constructive mathematics). In computability theory, the Church–Turing thesis (also known as the Church–Turing conjecture, Church s thesis, Church s… … Wikipedia
Optimization problem — In mathematics and computer science, an optimization problem is the problem of finding the best solution from all feasible solutions. Optimization problems can be divided into two categories depending on whether the variables are continuous or… … Wikipedia
Pseudo-polynomial time — In computational complexity theory, a numeric algorithm runs in pseudo polynomial time if its running time is polynomial in the numeric value of the input (which is exponential in the length of the input its number of digits).An ExampleConsider… … Wikipedia
Time complexity — In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the size of the input to the problem. The time complexity of an algorithm is commonly expressed using big O… … Wikipedia
Decomposition method (constraint satisfaction) — In constraint satisfaction, a decomposition method translates a constraint satisfaction problem into another constraint satisfaction problem that is binary and acyclic. Decomposition methods work by grouping variables into sets, and solving a… … Wikipedia
Decision tree model — In computational complexity and communication complexity theories the decision tree model is the model of computation or communication in which an algorithm or communication process is considered to be basically a decision tree, i.e., a sequence… … Wikipedia
